package com.c2b.algorithm.leetcode.lcr;

/**
 * <a href='https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/'>扁平化多级双向链表(Flatten a Multilevel Doubly Linked List)</a>
 * <p>你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。</p>
 * <p>给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。</p>
 * <p>返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * <a href='https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/'>查看示例</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>节点数目不超过 1000</li>
 *         <li>1 <= Node.val <= 10^5</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/20 11:07
 */
public class LCR028 {
    static class Solution {
        public Node flatten(Node head) {
            if (head == null) {
                return null;
            }
            Node dummyHead = new Node();
            dummyHead.next = head;
            Node currNode = head;
            while (currNode != null) {
                if (currNode.child != null) {
                    // 如果有子节点：先扁平化子节点,返回的是扁平化后链表的头节点
                    Node flattenListHead = flatten(currNode.child);
                    // 记录当前节点的下一个节点
                    Node nextNode = currNode.next;
                    // 接上当前链表
                    currNode.next = flattenListHead;
                    flattenListHead.prev = currNode;
                    currNode.child = null;
                    // 让当前节点来到扁平化链表的尾节点
                    while (currNode.next != null) {
                        currNode = currNode.next;
                    }
                    // 接上当前节点的后续节点
                    if (nextNode != null) {
                        currNode.next = nextNode;
                        nextNode.prev = currNode;
                    }
                }
                currNode = currNode.next;
            }
            return dummyHead.next;
        }
    }

    static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        Node node1 = new Node();
        Node node2 = new Node();
        Node node3 = new Node();
        Node node4 = new Node();
        Node node5 = new Node();
        Node node6 = new Node();
        Node node7 = new Node();
        Node node8 = new Node();
        Node node9 = new Node();
        Node node10 = new Node();
        Node node11 = new Node();
        Node node12 = new Node();

        node1.val = 1;
        node1.next = node2;
        node2.val = 2;
        node2.prev = node1;
        node2.next = node3;
        node3.val = 3;
        node3.prev = node2;
        node3.next = node4;
        node3.child = node7;

        node4.val = 4;
        node4.prev = node3;
        node4.next = node5;

        node5.val = 5;
        node5.prev = node4;
        node5.next = node6;

        node6.val = 6;
        node6.prev = node5;

        node7.val = 7;
        node7.next = node8;

        node8.val = 8;
        node8.prev = node7;
        node8.next = node9;
        node8.child = node11;

        node9.val = 9;
        node9.prev = node8;
        node9.next = node10;

        node10.val = 10;
        node10.prev = node9;

        node11.val = 11;
        node11.next = node12;

        node12.val = 12;
        node12.prev = node11;

        Node flatten = solution.flatten(node1);
        System.out.println();
    }
}
